//
// Created by francklinson on 2021/7/11 AT 23:09.
//
#include <iostream>
#include <queue>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};


class Solution {
public:
    TreeNode *addOneRow(TreeNode *root, int val, int depth) {
        if (depth == 1) {
            auto newRoot = new TreeNode(val, root, nullptr);
            return newRoot;
        }
        queue<TreeNode *> q;
        q.push(root);
        // 找到第depth-1层
        // 第一层已经放进去了 从第二层开始
        for (int depthNum = 2; depthNum < depth; ++depthNum) {
            unsigned int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                if (p->left != nullptr) q.push(p->left);
                if (p->right != nullptr) q.push(p->right);
            }
        }
        // 队列中剩下的就是第d-1层的节点 按规则进行添加即可
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            auto newLeftNode = new TreeNode(val, p->left, nullptr);
            auto newRightNode = new TreeNode(val, nullptr, p->right);
            p->left = newLeftNode;
            p->right = newRightNode;
        }
        return root;
    }
};

/**
 * 二叉树层序遍历
 * @param root
 * @return
 */
vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> ret;
    if (!root) {
        return ret;
    }
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = (int) q.size();
        ret.emplace_back();
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front();
            q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return ret;
}

int main() {
    auto n1 = TreeNode(4), n2 = TreeNode(2), n3 = TreeNode(6),
            n4 = TreeNode(3), n5 = TreeNode(1), n6 = TreeNode(5);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;
    Solution sol;
    auto ans = levelOrder(sol.addOneRow(&n1, 1, 2));
    for (auto &an : ans) {
        for (int j : an) {
            cout << j;
            cout << " ";
        }
        cout << endl;
    }


    return 0;
}

